package ua.mykola.ds.tree;

public class TreeToString {

	private static final char OPEN_BRACE = '{';
	private static final char CLOSE_BRACE = '}';
	private static final char SEPARATOR = ',';
	private static final String NULL_NODE = String.valueOf(OPEN_BRACE) + String.valueOf(CLOSE_BRACE);

	public String convertToString(Node toConvert) {
		StringBuilder sb = new StringBuilder();
		convertToString(toConvert, sb);
		return sb.toString();
	}

	private void convertToString(Node nodeToConvert, StringBuilder sb) {
		if (nodeToConvert == null) {
			sb.append(NULL_NODE);
		} else {
			sb.append(OPEN_BRACE);
			sb.append(nodeToConvert.value);
			convertToString(nodeToConvert.left, sb);
			sb.append(SEPARATOR);
			convertToString(nodeToConvert.right, sb);
			sb.append(CLOSE_BRACE);
		}
	}

	public Node convertToTree(String stringToConvert) {
		return convertToTree(stringToConvert, 0, stringToConvert.length());
	}

	private Node convertToTree(String stringToConvert, int begin, int end) {
		int separatorIndex = findSeparatorIndex(stringToConvert, begin + 1, end - 1);
		if (separatorIndex == -1)
			return null;
		int braceIndex = stringToConvert.indexOf(OPEN_BRACE, begin + 1);
		Node node = new Node(stringToConvert.substring(begin + 1, braceIndex));
		node.left = convertToTree(stringToConvert, braceIndex, separatorIndex - 1);
		node.right = convertToTree(stringToConvert, separatorIndex + 1, end - 1);
		return node;
	}

	private int findSeparatorIndex(String stringToConvert, int begin, int end) {
		int openBracesCounter = 0;
		int closedBracesCounter = 0;
		for (int i = begin; i < end; i++) {
			if (stringToConvert.charAt(i) == OPEN_BRACE)
				openBracesCounter++;
			else if (stringToConvert.charAt(i) == CLOSE_BRACE)
				closedBracesCounter++;
			if (openBracesCounter == closedBracesCounter && openBracesCounter > 0)
				return i + 1;
		}
		return -1;
	}
}
